package com.str.array;
public class Sorting {

  public static void bubbleSort(Comparable[] a) 
  { bubbleSort(a, 0, a.length-1); }

  private static void bubbleSort(Comparable[] a, int left, int right) {
  	trace("Initially:      ", a, left, right);
    for (int i = right; i > left; i--) {
      for (int j = left+1; j <= i; j++)
        if (a[j-1].compareTo(a[j]) > 0) {
          Comparable temp = a[j-1];
          a[j-1] = a[j];
          a[j] = temp;
        }
      trace("Iteration i = " + i + ":", a, left, right);
    }
  }

  public static void selectionSort(Comparable[] a) 
  { selectionSort(a, 0, a.length-1); }

  private static void selectionSort(Comparable[] a, int left, int right) {
    // Sort a[left...right].
    trace("Initially:      ", a, left, right);
    for (int i = left; i < right; i++) {
      int p = i;
      for (int j = i+1; j <= right; j++)
        if (a[j].compareTo(a[p]) < 0)
          p = j;
      if (p != i) {
      	Comparable temp = a[i];
        a[i] = a[p];  
        a[p] = temp;
      }
      trace("Iteration i = " + i + ":", a, left, right);
    }
  }

  public static void insertionSort(Comparable[] a)
  { insertionSort(a, 0, a.length-1); }
  
  private static void insertionSort(Comparable[] a, int left, int right) {
    // Sort a[left...right].
    trace("Initially:      ", a, left, right);
    for (int i = left+1; i <= right; i++) {
      Comparable val = a[i];
      int j = i;
      while (j > left && val.compareTo(a[j-1]) < 0) {
        a[j] = a[j-1];
        j--;
      }
      a[j] = val;
      trace("Iteration i = " + i + ":", a, left, right);
    }
  }

  public static void mergeSort(Comparable[] a) {
  	Comparable[] buffer = new Comparable[a.length];
    mergeSort(a, 0, a.length-1, buffer, true);
  }

  private static void mergeSort(Comparable[] a, int left, int right,
    Comparable[] b, boolean tracing) {
    // Sort a[left...right].
    if (tracing)
      trace("Initially:      ", a, left, right);
    if (left < right) {
      int mid = (left + right)/2;
      mergeSort(a, left, mid, b, false);
      if (tracing)
        trace("Left sorted:    ", a, left, right);
      mergeSort(a, mid+1, right, b, false);
      if (tracing)
        trace("Right sorted:   ", a, left, right);
      merge(a, left, mid, a, mid+1, right, b, left);
      for (int k = left; k <= right; k++)
        a[k] = b[k];
      if (tracing)
        trace("Merged:         ", a, left, right);
    }
  }

  private static void merge(
    Comparable[] a, int left1, int right1,
    Comparable[] b, int left2, int right2,
    Comparable[] c, int left3) {
    // Merge a[left1...right1] and b[left2...right2] into
    // c[left3...]  (where both a and b are sorted).
    int i = left1, j = left2, k = left3;
    while (i <= right1 && j <= right2)
      if (a[i].compareTo(b[j]) <= 0)
        c[k++] = a[i++];
      else
        c[k++] = b[j++];
    while (i <= right1)
      c[k++] = a[i++];
    while (j <= right2)
      c[k++] = b[j++];
  }

  public static void quickSort(Comparable[] a)
  { quickSort(a, 0, a.length-1, true); }

  private static void quickSort(Comparable[] a, int left, int right,
    boolean tracing) {
    // Sort a[left...right].
    if (tracing)
      trace("Initially:      ", a, left, right);
    if (left < right) {
      int p = partition(a, left, right);
      if (tracing)
        trace("Partitioned:    ", a, left, right);
      quickSort(a, left, p-1, false);
      if (tracing)
        trace("Left sorted:    ", a, left, right);
      quickSort(a, p+1, right, false);
      if (tracing)
        trace("Right sorted:   ", a, left, right);
    }
  }

  private static int partition(Comparable[] a, int left, int right) {
    // Partition a[left...right] such that
    // a[left...p-1] are all less than or equal to a[p] and
    // a[p+1...right] are all greater than or equal to a[p].
    Comparable pivot = a[left];
    int p = left;
    for (int r = left+1; r <= right; r++)
      if (a[r].compareTo(pivot) < 0) {
        a[p] = a[r];
        a[r] = a[++p];
      }
    a[p] = pivot;  
    return p;
  }

  private static void trace(String caption, Object[] a,
	int left, int right) {
    System.out.print(caption + " {");
    for (int k = left; k <= right; k++)
      System.out.print(" " + a[k]);
    System.out.println(" }");
  }

  public static void main(String[] args) {
    String[] word1 = {"dog", "cat", "rat", "pig", "fox", "eel", "ant",
      "hen", "bat" };
    String[] word2;

    System.out.println("Bubble sort:");
    word2 = (String[]) word1.clone();
    bubbleSort(word2);

    System.out.println("\nSelection sort:");
    word2 = (String[]) word1.clone();
    selectionSort(word2);

    System.out.println("\nInsertion sort:");
    word2 = (String[]) word1.clone();
    insertionSort(word2);

    System.out.println("\nMerge-sort:");
    word2 = (String[]) word1.clone();
    mergeSort(word2);

    System.out.println("\nQuick-sort:");
    word2 = (String[]) word1.clone();
    quickSort(word2);
  }
}
